class Solution {
    public:
        int ret = 0,_m,_n,_cnt;
        int is_existent[100][100];
        int sum_eachdigit(int i){
            int sum = 0;
            while(i){
                sum+=i%10;
                i /= 10;
            }
            return sum;
        }
        int wardrobeFinishing(int m, int n, int cnt) {
            _m = m;_n = n; _cnt = cnt;
            dfs(0,0);
            return ret;
        }
        int indexx[2] = {0,1};
        int indexy[2] = {1,0};
        void dfs(int i,int j){
            int sum = sum_eachdigit(i)+sum_eachdigit(j);
            is_existent[i][j] = 1;
            if(sum > _cnt){
                return;
            }else{
                ret++;
            }    
            for(int k = 0 ; k < 2 ; k++){
                int row = i+indexx[k];
                int col = j+indexy[k];
                if(row >= 0 && row < _n&& col >=0 && col < _m && is_existent[row][col] ==0 ){
                    dfs(row,col);
                }
            }
        }
    
    };